/**
 * 328. 奇偶链表
 * https://leetcode-cn.com/problems/odd-even-linked-list/
 */
public class Solutions_328 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode cur = head;
        cur.next = new ListNode(2);
        cur = cur.next;
        cur.next = new ListNode(3);
        cur = cur.next;
        cur.next = new ListNode(4);
        cur = cur.next;
        cur.next = new ListNode(5);  // output: {1,3,5,2,4}

        ListNode result = oddEvenList(head);
        System.out.println(result);
    }

    // 模拟 + 迭代
    public static ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next == null) {
            // 链表结点数量不足 3 个的情况，直接返回
            return head;
        }
        // 修改 odd 即是修改 head
        ListNode odd = head;  // 奇数索引位链表头结点的变化结点

        ListNode even = head.next;  // 偶数索引位链表的头结点
        ListNode evenCur = even;  // 偶数索引位链表结点的变化结点

        /**
         * 设有结点 {1, 2, 3, 4}
         * 1 结点后接结点 3，奇数结点变换为结点 3
         * 2 结点后接结点 4（奇数结点 3 的下一位）
         */
        while (odd.next != null && evenCur.next != null) {
            odd.next = evenCur.next;
            odd = odd.next;
            evenCur.next = odd.next;
            evenCur = evenCur.next;
        }
        // 偶数链表头结点作为奇数链表尾结点的下一节点
        odd.next = even;
        // 原地修改 head 后，返回 head
        return head;
    }
}
